package leetcode_题库;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/26 9:36 星期五
 */
public class _94_二叉树的中序遍历 {
    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;


//        List<Integer> nn = inorderTraversal(n1);
        List<Integer> nn = inorderTraversalDeep(n1);
        System.err.println(nn);
    }

    /**
     * 迭代
     * > 2022/08/26 10:39:03
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:39.7 MB,击败了46.89% 的Java用户
     * @param root
     * @return
     */
    private static List<Integer> inorderTraversalDeep(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        //定义返回数组和栈
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        //无论如何，我们将根结点入栈
        stack.push(root);
        //定义一个指针，帮助我们定位current，中序遍历先遍历左结点，因此，我们让cur成为root的左子结点
        TreeNode cur = root.left;
        while (!stack.isEmpty()) {
            //cur不为空，再向左
            if (cur != null) {
                //将当前结点入栈，然后继续向左子结点迭代
                stack.push(cur);
                cur = cur.left;
            } else {
                //当前结点为空，创建临时指针pre，存储当前结点的上一结点（父结点）
                TreeNode pre = stack.pop();
                //出栈（因为pre是树中最后一个左叶子结点）
                list.add(pre.val);
                //pre的右子结点不为空
                if (pre.right != null){
                    //将pre的右子结点入栈
                    stack.push(pre.right);
                    //我们要保证cur指针在左子结点上，我已我们让cur位于新入栈元素的左子结点，也就是pre.right.left
                    cur = pre.right.left;
                }
            }
        }
        return list;
    }

    /**
     * 递归
     * > 2022/08/26 09:46:02
     * 解答成功:
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:39.3 MB,击败了97.12% 的Java用户
     *
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        return inorderTraversal(root, new ArrayList<Integer>());
    }

    private static List<Integer> inorderTraversal(TreeNode root, ArrayList<Integer> list) {
        if (root == null) {
            return new ArrayList<>();
        }
        inorderTraversal(root.left, list);
        list.add(root.val);
        inorderTraversal(root.right, list);
        return list;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
